package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseKGroup(head *ListNode, k int) *ListNode {

	// 创建一个虚拟头结点以简化边界情况的处理
	hair := &ListNode{Next: head}
	pre := hair

	// 定义一个辅助函数用于反转链表的一部分
	reverse := func(start, end *ListNode) {
		prev := end.Next
		curr := start
		for prev != end {
			next := curr.Next
			curr.Next = prev
			prev = curr
			curr = next
		}
	}

	for head != nil {
		// 初始化尾节点为当前位置
		tail := pre
		// 移动尾节点到第 k 个节点
		for i := 0; i < k; i++ {
			tail = tail.Next
			// 如果剩余节点不足 k 个，则无需反转，直接返回结果
			if tail == nil {
				return hair.Next
			}
		}
		// 保存反转后的下一组的起始节点
		nextGroup := tail.Next
		// 反转当前组，并更新头尾节点
		reverse(head, tail)
		// 连接反转后的组到前面的部分
		pre.Next = tail
		// 连接反转后的尾节点到下一组的起始节点
		head.Next = nextGroup
		// 更新 pre 到当前组的尾节点
		pre = head
		// 更新 head 到下一组的起始节点
		head = nextGroup
	}
	// 返回从虚拟头结点开始的修改后的链表
	return hair.Next
}

func printlist(head *ListNode) {
	for head != nil {
		fmt.Printf("%d", head.Val)
		head = head.Next
	}
}
func main() {

	l := ListNode{Val: 1}
	l.Next = &ListNode{Val: 2}
	l.Next.Next = &ListNode{Val: 3}
	l.Next.Next.Next = &ListNode{Val: 4}
	l.Next.Next.Next.Next = &ListNode{Val: 5}
	printlist(reverseKGroup(&l, 3))
}
